Черв'яки Патерсона

Червяки Патерсона (англ. Paterson's worms) — сімейство клітинних автоматів типу тюрмітів, вигадане в 1971 році британським вченим Майклом Патерсоном для моделювання поведінки і годівлі деяких доісторичних черв'яків. Незважаючи на простий набір правил, поведінка автоматів може бути дуже складною, і для жодного з наборів правил його доля невідома.

Історія

Рештки шляхів черв'яків

Доісторичні хробаки харчувалися падаллю на дні ставків і уникали повторного проходження своїх шляхів, оскільки там було мало їжі. Проте їжа зустрічалася купками, тому вони прагнули триматися поблизу вже пройдених шляхів. При цьому різним видам черв'яків були властиві різні правила, які визначали, наскільки близько до пройдених шляхів триматися, коли і як різко повертати.

У 1969 році Давид Рауп і Адольф Зайлахер створили комп'ютерну симуляцію копалин слідів хробаків, що надихнуло Патерсона і Джона Конвея на пошук простих моделей клітинних автоматів для дослідження ідеалізованих черв'яків на решітці. Конвей пропонував досліджувати черв'яків на квадратній решітці, однак там були всього три види черв'яків з досить нудною поведінкою, а Патерсон запропонував використовувати трикутну решітку.

Опис

В цій моделі черв'як повзає по трикутної решітці, межі якої зображують їжу, і при проходженні грані вона зафарбовується («з'їдається»). У кожній вершині черв'як обирає, уздовж якої грані йому направлятися, виходячи з того, які з шести граней, що примикають до вершини, зафарбовані. Напрямки відраховуються з точки зору хробака. Черв'як помирає, якщо у вершині немає назафарбованих («нез'їдених») граней, що, втім, можливо тільки в початковому стані з міркувань парності.

Правила задані заздалегідь і визначають конкретний клітинний автомат в сімействі («вид хробака»), проте часто вважається, ніби черв'як приймає рішення на кожному кроці, але якщо він вже зіштовхувався з подібною ситуацією, то зобов'язаний прийняти теж саме рішення.

Нумерація правил

Нумерація напрямків — черв'як рухається від лівого краю до центру

Черв'як Патерсона з правилом {2, 0, 0}

Правила можуть бути класифіковані завданням напрямків, які черв'як обирає, вперше «стикаючись» з незнайомою ситуацією, в порядку виникнення цих ситуацій. Напрямки зазвичай нумерують за годинниковою стрілкою, починаючи з 0 — напрямки вперед (див. зображення зліва). При цьому черв'як не може вибрати напрямок 3 — повернути назад. Також зазвичай не вказуються вибори, які черв'яку не доведеться зробити, оскільки він вмирає раніше, і вважається, що перший поворот черв'як робить вправо, оскільки випадок лівого повороту симетричний.

Наприклад, правило {2, 0, 0}, що задає хробака, зображеного праворуч, каже, що при першому виборі (всі 5 напрямків незафарбовані) черв'як повертає направо-назад, а при двох наступних (зафарбовано напрямок направо-назад і зафарбовані напрямки наліво вперед, наліво-назад і направо назад відповідно) обирає рух прямо. Подальші його вибори не вказані, оскільки черв'як втретє повертається в початок і помирає. Якщо обмежитися випадками, в яких черв'як робить перший поворот направо, то потенційно існує 1 296 можливих правил. Однак з урахуванням того, що черв'як часто вмирає, не встигнувши здійснити всі можливі вибори, а тому немає сенсу відрізняти ці правила, їх залишається всього 412. Серед них 336 кінцеві, 73 нескінченні і циклічно повторюються із зсувом, для двох нескінченність не доведена, але припускається (це правила {1,0,4,2,0,2,0} і {1,0,4,2,0, 1,5}), а поведінка ще одного невідома (правило {1,0,4,2,0,1,5}).